package middle;

public class Solution_695 {
    boolean[][] visited;
    int[][] directs = new int[][]{{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
    public int maxAreaOfIsland(int[][] grid) {
        visited = new boolean[grid.length][grid[0].length];
        int max = 0;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[i].length; j++) {
                if (!visited[i][j] && grid[i][j] == 1) {
                    int count = dps(grid, i , j);
                    max = Math.max(max, count);
                }
            }
        }
        return max;
    }

    private int dps(int[][] grid, int i, int j) {
        if (i < 0 || i >= grid.length || j < 0 || j >= grid[0].length) {
            return 0;
        }
        int count = 0;
        if (!visited[i][j] && grid[i][j] == 1) {
            count++;
            visited[i][j] = true;
            for (int[] direct : directs) {
                count += dps(grid, i + direct[0], j + direct[1]);
            }
        }
        return count;
    }

    public static void main(String[] args) {
        Solution_695 model = new Solution_695();
        System.out.println(model.maxAreaOfIsland(new int[][]{{0,0,1,0,0,0,0,1,0,0,0,0,0},{0,0,0,0,0,0,0,1,1,1,0,0,0},{0,1,1,0,1,0,0,0,0,0,0,0,0},{0,1,0,0,1,1,0,0,1,0,1,0,0},{0,1,0,0,1,1,0,0,1,1,1,0,0},{0,0,0,0,0,0,0,0,0,0,1,0,0},{0,0,0,0,0,0,0,1,1,1,0,0,0},{0,0,0,0,0,0,0,1,1,0,0,0,0}}));
    }
}
